package leetcode.code;

import java.util.ArrayList;
import java.util.List;

public class Solution119 {

	public List<Integer> getRow(int rowIndex) {
		List<Integer> row = new ArrayList<>();// 每一行
		row.add(1);
		if (rowIndex == 0)
			return row;
		int numRows = rowIndex + 1;
		int len = (numRows + 1) * numRows / 2; // 总数量
		int[] arr = new int[len]; // 三角数据
		arr[0] = 1; // 第一个数据1
		int off = 1;// 当前行之前一共多少个数, 偏移量
		for (int i = 2; i <= rowIndex; i++) {
			arr[off] = 1;// 每一行第一个是1
			for (int j = off + 1; j < i + off - 1; j++) {// 当前行除去首尾的一般部分
				arr[j] = arr[j - i] + arr[j - i + 1];// 一般位置的状态转移
			}
			arr[i + off - 1] = 1;// 每一行最后一个是1
			off += i; // 更新偏移量
		}
		for (int j = off + 1; j < numRows + off - 1; j++) {// 当前行除去首尾的一般部分
			arr[j] = arr[j - numRows] + arr[j - numRows + 1];// 一般位置的状态转移
			row.add(arr[j]);
		}
		row.add(1);
		return row;
	}

	public static void main(String[] args) {
		Solution119 so = new Solution119();
		so.getRow(5);

	}

}
